#include <iostream>
using namespace std;
typedef struct ArcNode{
  int adjvex;
  int weight;
  ArcNode *next;
}ArcNode;

typedef struct VertexNode{
  char vertex;
  ArcNode *firstarc;
}VertexNode,AdjList[100];

typedef struct GraphAdjList{
  AdjList adjlist;
  int vexnum;
  int arcnum;
}GraphAdjList;


void createGraphAdjList(GraphAdjList &G){
  cin >> G.vexnum >> G.arcnum;
  for(int i = 0; i < G.vexnum; i++){
    cin >> G.adjlist[i].vertex;
    G.adjlist[i].firstarc = NULL;
  }
  
  ArcNode *p;
  for(int k = 0; k < G.arcnum; k++){
    int i,j,w;
    cin >> i >> j >> w;
    p = new ArcNode;
    p->adjvex = j;
    p->weight = w;
    p->next = G.adjlist[i].firstarc; //头插法 
    G.adjlist[i].firstarc = p;
  }
  
}

void transOutToIn(GraphAdjList gOut,GraphAdjList &gIn){
  
  gIn.vexnum =  gOut.vexnum; //初始化逆邻接表顶点数目   
  gIn.arcnum =  gOut.arcnum; //初始化逆邻接表边数目  
  
  for(int i = 0; i < gOut.vexnum; i++){
    gIn.adjlist[i].vertex = gOut.adjlist[i].vertex;//构造逆邻接表顶点向量 
    gIn.adjlist[i].firstarc = NULL;
  }
  
  for(int i = 0; i < gOut.vexnum; i++){
    ArcNode *p,*s;
    int j;
    
    p = gOut.adjlist[i].firstarc;//取出邻接表中第i个顶点的指向邻接表的指针   
    
    while(p){  //遍历邻接表中第i个顶点所有邻接边 
        j = p->adjvex;  
        s = new ArcNode;
        s->adjvex = i;//将 i 挂到 gIn.adjlist[j]上
        s->weight = p->weight;
        s->next = gIn.adjlist[j].firstarc; //将 i 挂到 j上 ,头插法
        gIn.adjlist[j].firstarc = s;
        p = p->next;
    }
  }
  

}

void printfGraphAdjList(GraphAdjList G){
    for(int i = 0; i < G.vexnum; i++){
      ArcNode *p = G.adjlist[i].firstarc;
      cout << G.adjlist[i].vertex << "\t";
      while(p){
        cout << G.adjlist[p->adjvex].vertex << " " << p->weight << "\t";
        p = p->next;
      }
    
      cout << endl;
    }
    
    
}

int main(){
  
  GraphAdjList gOut,gIn;//gOut邻接表  gIn逆邻接表 
  createGraphAdjList(gOut);//构造邻接表 
  printfGraphAdjList(gOut);//打印邻接表 
  transOutToIn(gOut,gIn); //由邻接表转化为逆邻接表  
  printfGraphAdjList(gIn);//打印逆邻接表 
  return 0;
   
}
